package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.ArrayDeque;

/**
 * @author: ZhouBert
 * @date: 2021/2/23
 * @description: 1008. 前序遍历构造二叉搜索树
 * https://leetcode-cn.com/leetbook/read/algorithm-and-interview-skills/xu1q2h/
 */
public class B_1008_前序遍历构造二叉搜索树 {

	public static void main(String[] args) {
		B_1008_前序遍历构造二叉搜索树 action = new B_1008_前序遍历构造二叉搜索树();
//		test1(action);
		test2(action);
	}

	public static void test1(B_1008_前序遍历构造二叉搜索树 action) {
		// true
		int[] preorder = {8, 5, 1, 7, 10, 12};
		TreeNode res = action.bstFromPreorder(preorder);
		System.out.println("res = " + res);
	}

	public static void test2(B_1008_前序遍历构造二叉搜索树 action) {
		// true
		int[] preorder = {1, 3, 2};
		TreeNode res = action.bstFromPreorder(preorder);
		System.out.println("res = " + res);
	}

	/**
	 * 这个题目有点不太好理解：
	 * 给定的 preorder 是一个前序遍历的数组，并且通过 二叉搜索树的性质保持唯一性
	 * --
	 * 通过模拟，找到了一个规律：
	 * 当确定了跟节点的位置之后，就不会再去找之前的跟节点
	 *
	 * @param preorder 前序遍历的结果
	 * @return
	 */
	public TreeNode bstFromPreorder(int[] preorder) {
		int len = preorder.length;
		TreeNode root = new TreeNode(preorder[0]);
		ArrayDeque<TreeNode> stack = new ArrayDeque<>();
		stack.addLast(root);
		TreeNode cur = root, newNode;
		for (int i = 1; i < len; i++) {
			newNode = new TreeNode(preorder[i]);
			boolean flag =false;
			//似乎能够保证 栈一定不为空，因为每一次都会往栈里增加元素
			//由于所给的数值各不相同，所以不需要考虑 =
			while (!stack.isEmpty() && preorder[i] > stack.peekLast().val) {
				//大于 栈顶元素
				cur = stack.removeLast();
				flag = true;
			}
			if (!flag){
				cur = stack.peekLast();
			}
			if (preorder[i] > cur.val) {
				cur.right = newNode;
			} else {
				//此时 小于栈顶元素
				cur.left = newNode;
			}
			stack.addLast(newNode);

		}
		return root;

	}
}
